package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayList;
import java.util.List;

//给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，
// 计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
// 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
//
// 示例 1：
//
//输入：expression = "2-1-1"
//输出：[0,2]
//解释：
//((2-1)-1) = 0
//(2-(1-1)) = 2
//
// 示例 2：
//输入：expression = "2*3-4*5"
//输出：[-34,-14,-10,-10,10]
//解释：
//(2*(3-(4*5))) = -34
//((2*3)-(4*5)) = -14
//((2*(3-4))*5) = -10
//(2*((3-4)*5)) = -10
//(((2*3)-4)*5) = 10
//
// 提示：
// 1 <= expression.length <= 20
// expression 由数字和算符 '+'、'-' 和 '*' 组成。
// 输入表达式中的所有整数值在范围 [0, 99]
// Related Topics 递归 记忆化搜索 数学 字符串 动态规划
// 👍 760 👎 0

public class Solution241 {
	public List<Integer> diffWaysToCompute1(String expression) {
		List<Integer> ans = new ArrayList<>();
		List<Character> a = new ArrayList<>();
		List<Character> b = new ArrayList<>();
		for (char c : expression.toCharArray()) {
			if ('0' <= c && c <= '9') {
				a.add(c);
			} else {
				b.add(c);
			}
		}
		for (int i = 0; i < a.size(); i++) {
			ans = dfs(a, b, 0, a.size() - 1);
		}
		return ans;
	}

	public List<Integer> dfs(List<Character> a, List<Character> b, int left, int right) {
		if (left == right) {
			return new ArrayList<>(a.get(left));
		}
		List<Integer> res = new ArrayList<>();
		for (int i = left; i <= right; i++) {
			List<Integer> lr = dfs(a, b, left, i);
			List<Integer> rr = dfs(a, b, i + 1, right);
			for (Integer li : lr) {
				for (Integer ri : rr) {
					if (b.get(i) == '+') {
						res.add(li + ri);
					} else if (b.get(i) == '-') {
						res.add(li - ri);
					} else {
						res.add(li * ri);
					}
				}
			}
		}
		return res;
	}





















	// f(i) = f(i-1) + f(i-2) + f(i-3)  + ...+ f(0)
	// f(i,j) = f(i,j-1) 笛卡尔乘积 f(j,j) , f(i,j-2) * f(j-2,j) ..... f(i,i) * f(i+1,j)
	char[] cs;

	public List<Integer> diffWaysToCompute(String expression) {
		cs = expression.toCharArray();
		return dfs(0, cs.length - 1);
	}

	public List<Integer> dfs(int l, int r) {
		List<Integer> ans = new ArrayList<>();
		for (int i = l; i <= r; i++) {
			if (cs[i] >= '0' && cs[i] <= '9') continue;
			List<Integer> l1 = dfs(l, i - 1), l2 = dfs(i + 1, r);
			for (int a : l1) {
				for (int b : l2) {
					int cur = 0;
					if (cs[i] == '+') cur = a + b;
					else if (cs[i] == '-') cur = a - b;
					else cur = a * b;
					ans.add(cur);
				}
			}
		}
		if (ans.isEmpty()) {
			int cur = 0;
			for (int i = l; i <= r; i++) cur = cur * 10 + (cs[i] - '0');
			ans.add(cur);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution241 solution = new Solution241();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
//		System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
		System.out.println(solution.diffWaysToCompute("2-1-1"));
	}

}
